介紹

non-volatile memory (NVM)非揮發性記憶體

優點：

• higher cell density ->可以存放更多空間
• lower power consumption->不用靠著週期性充電來存放資料
• read performance與RAM差不多

缺點：

• limited write endurance-->寫入壽命低
• The asymmetric properties of NVM read/write operations may also largely limit the feasibility of performing machine learning algorithms directly on NVM

有可能取代DRAM的NVM

• spin-transfer torque magnetic random access memory (STT-RAM or STT-MRAM)
• resistive random access memory (ReRAM)
• phase-change memory (PCM)

Random forest (or random decision forest)

• 應用
  supervised and ensemble learning algorithm for both classification and regression problems, which constitute the majority of machine learning applications or systems nowadays.
  
• bagging process
  隨機選擇一定數量的來自訓練數據集的數據樣本形成和訓練decision trees，bagging process通常運行幾輪形成decision tree forest。值得注意的是，每輪bagging使用的選定數據樣本將被放回原位並可能被下一輪使用。bagging保證多個decision trees的隨機性。
• vote
  在建立了多個獨立的decision trees之後，一個隨機的forest 可以對分類任務進行多數投票或對個人決策的所有估計取平均值回歸問題的樹有一個更準確和穩定的預測。
• 優點
  當子樹夠多，通常隨機森林不會over-fit the model or training dataset

論文動機

因隨著數據的生成爆炸性地，隨機森林算法需要處理數據集的大小迅速增加，並且可能面臨保持數量飆升數據樣本到main memory的困難。
而現實中龐大的數據集可能首先保存在secondary storage(SSD)，透過swap in-and-out between the faster-but-smaller main memory and the slower but-larger secondary storage。
儘管如此，這種解決方案可能不可避免地導致頻繁的數據交換，這可能會嚴重降低隨機森林的構建/訓練階段中的runtime performance。
而頻繁的swapping導不但導致NVM的壽命縮短還會使runtime performance下降以及耗電上升此外發現隨機森林很有可能選取不同子樹但是是同比資料造成不必要的data swapping因此提出MVN-friendly bagging strategy

論文目的

協調具有NVM特性的機器學習算法的特殊數據access pattern，從而最終將 NVM write minimize使得secondary storage to main memory之間不必要的數據交換和續航優化。

MVN-friendly bagging strategy

核心概念

可以積極地重複使用data在bagging process過程中，並且不影響prediction accuracy of a random forest。

方法

• Design Concept: Sampled Data Reusing
  每次寫入新的round時，random reusing data可以使寫入次數下降，但是會有Wear Un-leavling(寫入的block是不平均的進而導致經常重複寫入的block壽命較短)的問題發生，因此我們的設計理念需要修改。
  

• Marching Based Reusing Policy(MRP)
  上述提到的問題透過MRP來解決，選擇一個樞紐將reusing data和random access data拆成兩個部分，而下一次則是將上一次的random access data當作reuse data，樞紐的終止條件為當reuse frame=random frame時也就是上圖中的3rd Round，從結果來看這個方法不但可以降低寫入次數還能使得Wear Leveling，增加block的平均壽命。

論文結果

使用數據

• Adult dataset is used to predict whether a person earns over 50,000 USD a year by considering attributes,such as age, education, occupation, sex and race.
• Dota2 dataset is used to predict the winner among two competitive teams (5 members for each team) by considering attributes,such as game type, game mode and the hero identification.
• Poker dataset is used to predict a hand consisting of five playing cards (such as full house and royal flush) drawn from a standard deck of 52 poker cards by considering attributes, such as ordinal and numerical.

每個data區分成70% training data、30% testing data並用testing data的ACC來驗證reuse data不會影響ACC。

圖表分析

• data reused ratio is the ratio between the size of reused data and the selected data.
• 分別有0%、25%、50%、75%、100%

write與reuse ratio的關係

首先上圖(Fig. 3)可以看出當reuse ratio越高，write的次數可以下降因為可以減少在main memory與secondary storage之間的data movement。

ACC與reuse ratio的關係

而上圖(Fig. 4)可以看出當reuse ratio不要超過75%時幾乎可以跟0%有著一樣的ACC。

ACC與tree size和reuse ratio的關係

因許多研究指出[1]random forest may not always be beneficial to the forest
size (e.g., the number of the decision trees).而上圖(Fig. 5)可以看出當reuse ratio不要超過75%時幾乎可以跟0%有著一樣的ACC，即便改變tree size也一樣。

結論

本篇論文使用了NVM-friendly bagging strategy去降低寫入次數及解決Wear Un-leavling的問題，最終此設計最多可節省72%的寫入訪問且幾乎不影響ACC。
$$ 0.72 = \frac{寫入數量當reuse-ratio=0-寫入數量當reuse-ratio=0.75}{寫入數量當reuseratio=0} $$

參考資料

[1] Thais Mayumi Oshiro, Pedro Santoro Perez, and Jos´e Augusto Baranauskas. How many trees in a random forest? In International workshop on machine learning and data mining in pattern recognition,pages 154–168. Springer, 2012.
[2] Y. T. Ho, C. -F. Wu, M. -C. Yang, T. -Y. Chen and Y. -H. Chang, "Replanting Your Forest: NVM-friendly Bagging Strategy for Random Forest," 2019 IEEE Non-Volatile Memory Systems and Applications Symposium (NVMSA), Hangzhou, China, 2019, pp. 1-6, doi: 10.1109/NVMSA.2019.8863525.